#include <iostream>
#include <vector>
#define MAX_CHAR_SIZE 26
using namespace std;
class Trie
{
private:
   bool isLeaf;
   vector<Trie *> child = vector<Trie *>(MAX_CHAR_SIZE, nullptr);

public:
   Trie(/* args */) : isLeaf(false)
   {
      // isLeaf=false;
   }
   void insert(string word)
   {
      Trie *p = this;
      for (auto &w : word)
      {
         int t = w - 'a';
         if (!p->child[t])
            p->child[t] = new Trie();
         p = p->child[t];
      }
      p->isLeaf = true;
   }

   bool search(string word)
   {
      Trie *p = this;
      for (auto &w : word)
      {
         int t = w - 'a';
         if (!p->child[t])
            return false;
         p = p->child[t];
      }
      return p->isLeaf;
   }

   bool startWith(string word)
   {
      Trie *p = this;
      for (auto &w : word)
      {
         int t = w - 'a';
         if (!p->child[t])
            return false;
         p = p->child[t];
      }
      return true;
   }
   ~Trie();
};

Trie::Trie(/* args */)
{
}

Trie::~Trie()
{
}

int main()
{
   Trie trie;
   trie.insert("apple");
   cout << trie.search("apple") << endl;
   cout << trie.search("app") << endl;
   cout << trie.startWith("app") << endl;
   trie.insert("app");
   cout << trie.search("app") << endl;
   system("pause");
   return 0;
}
